COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\sneakhead{Avoiding Redundant Effort in Programming}
C00008 ENDMK
C⊗;
\sneakhead{Avoiding Redundant Effort in Programming}
\sendindex{Redundant Effort} 

     Suppose we have read into an array  {\tt NAME[1..100]}  the names of the players
in a tournament, and into {\tt SCORE[1..100]} their scores.  Now we want the program
to print out the name of the player with the highest score (we will assume the
scores are all different, for simplicity).  One approach is to try each player
in turn, and check his score against all the scores, printing his name if no
other score is higher.  A program to do this might be:

\sendnotes{RWF- The program here is buggy.  Need to discuss the AND problem in Pascal}
\startcode
        (declarations)
        BEGIN
        FOR P:=1 TO 100 DO 
           BEGIN
           (* CHECK IF P IS WINNER *)
           Q:=1;
           WHILE (Q <= 100) AND (SCORE[P] > SCORE[Q]) DO 
              BEGIN
              (* P BEATS PLAYERS UP TO Q *)
              Q := Q+1
              END;
           IF Q > 100 THEN WRITE(NAME[P])
           END
        END.
\endcode

     This program is correct, but needlessly complex, and can run as many as
five thousand times through the inner iteration (if the scores are in
increasing order).  The program does not have the common sense knowledge built
in that we would have; if player  P  beats everybody on the list before
player  Q, then nobody before player  Q  has any chance, and we should
continue by comparing player  Q's  score against those of all the following
players on the list.  So we need to inspect the list only once, remembering only
two facts about the part of the list we have already seen:  the best score
so far, and who had it.

     A program based on this idea is the following:

\startcode
        (declarations, etc.)
        BEGIN
        BESTPLAYER := NAME[1];
        BESTSCORE := SCORE[1];
        FOR I:=2 TO 100 DO 
           IF SCORE[I] > BESTSCORE THEN 
              BEGIN
              BESTSCORE := SCORE[I];
              (* BEST OF FIRST I SCORES *)
              BESTPLAYER := NAME[I];
              (* BEST OF FIRST I PLAYERS *)
              END
        END;
        WRITE(BESTPLAYER)
        END.
\endcode

The general idea is to record all the useful information that can be kept from
the part of the computation done so far.

\sendnotes{dpb->rwf: compute e for small value of x?}
     Suppose we want to compute  e  for a small value of  x, using the
formula:
$$e = 1 +{x\over1!}+{x↑{2}\over2!}+{x↑{3}\over3!}+{x↑4\over4!}+\cdots+{x↑9\over9!}$$
The most obvious method uses an outer iteration to run through the terms which
are being added, and an inner iteration to calculate the factorials.  This
involves much wasted effort, because when we have computed 3! we don't
have to start from scratch to compute 4!; we only have to multiply 3!
by 4.  In fact, once we have $x↑3/3!$, we only have to multiply by $x$ and
divide by  4 to get $x↑4/4!$. A program based on this follows:

\startcode
        (declarations)
        BEGIN
        READ(X);
        SUM := 1;
        TERM := 1;
        FOR I:=1 TO 9 DO 
           BEGIN
           TERM := TERM * X/I; (*  X**I/I! *)
           SUM := SUM + TERM  (* SUM OF TERMS UP TO DEGREE I *)
           END;
        END.
\endcode

     Again, we have arranged to keep all the information we can for later use.
The variable {\tt TERM} holds enough useful information that we can get the new
summand at the next value of {\tt I} with just a multiplication and division.